連想ストレージのシステムと方法

专利摘要:
クライアントから受信したファイルなどの情報は、連想ストレージ装置などのストレージ装置内に保存されている。ファイルサーバはクライアントからデータを受信し、データを複数のデータのブロックの塊にする。ファイルサーバは、データ構造を構成するときに使用するためにメタデータも生成する。複数のデータのブロックは、ブロックストアに保存され、複数のデータブロックとメタデータのコピーは、ファイルサーバにローカルにキャッシュされている。コミットサーバはメタデータを検索する。少なくとも１つの実施形態において、メタデータは、ファイルサーバとコミットサーバとの間で共有されている更新ログから検索される。検索されたメタデータに基づいて、コミットサーバはデータ構造のバージョンを生成する。それからデータ構造はブロックストアに保存される。
公开号:JP2011513853A
申请号:JP2010549626
申请日:2008-03-17
公开日:2011-04-28
发明作者:ベンジャミン アトキン、；クリスチャン アングレアーヌ、；グルゼゴルツ カルコウスキ、；セザリー ダブニッキ、
申请人:エヌイーシー ラボラトリーズ アメリカ インクＮＥＣ Ｌａｂｏｒａｔｏｒｉｅｓ Ａｍｅｒｉｃａ， Ｉｎｃ．；
IPC主号:G06F12-00

专利说明:

[0001] 本発明は、一般に、連想ストレージに関し、特に、連想ストレージシステム内のデータへの改善されたアクセスに関する。]
背景技術

[0002] 大量のデータの保存は、ビジネスにとって重大である。ビジネスアプリケーションの中でも特にファイルシステムは、バックアップしなければならず、大量のレコードは、法的な要求事項を満たすように保持しなければならず、データの大量の集合は保存しなければならない。この重要なデータは、ハードウェア障害に対して早く回復できるように、保存しなければならない。これらのデータの集まりの各々の特定の要求に対応しているさまざまな装置が採用されている。]
[0003] 以前には、連想ストレージ（ＣＡＳ）が、高容量ストレージ装置の構築に使用されてきた。ＣＡＳ装置は、データブロックの内容にハッシュ関数を適用することによって、データのブロックに対してアドレスを生成する。これによって、ＣＡＳ装置がデータブロックの１つのコピーを保存するだけでよいように、データブロックの複製コピーを容易に特定することができる。ストレージの要件を少なくすることによって、ＣＡＳ装置を高容量ストレージに役立つようにすることができる。]
発明が解決しようとする課題

[0004] しかし、ＣＡＳは、不変のオブジェクトを通常保存するため、ＣＡＳは、無閉路有向グラフ（ＤＡＧ）内に編成されているデータの書き込みだけが可能である。つまり、親ブロックが子ブロック（のたとえばアドレス）をいったん指すと、子ブロックは親ブロックを指すことはできない。子が多くの親から指されている共有の側面を無視すると、これらのＤＡＧは、非公式には「木」と呼ぶことができる。保存されたデータを修正可能にする（例えば、ファイルを上書きできるようにする）ストレージ装置を実装するためにＣＡＳを使用するには、２つの重要な課題がある。（１）ストレージをどのようにして効果的に利用するか（たとえば、変化しているデータ／リーフ／子ブロックの集合を指す親ブロックの使用を最小化する）と、（２）より高い性能を実現するために、木の異なる部分の並列の修正（例えば過度のロックを避けること）をどのようにして実現するかである。それゆえに、連想ストレージ装置内でのデータの保存と検索の改良された装置と方法とが必要になる。]
課題を解決するための手段

[0005] 本発明は、一般に、下位の連想ストレージを使用して情報を効率的に保存する装置と方法とを提供する。クライアントから受信したファイルなどの情報は、連想ストレージ装置などのストレージ装置内に保存されている。ファイルサーバは、クライアントから、データを受信する（例えばデータをファイルに追加する）、および／または、ファイルの作成や削除などのメタデータ操作を受信する。データは、ブロックストアのデータブロックストレージに保存される複数のデータブロックに、グループ分けされる。データ書き込み操作によってファイルシステムメタデータが修正されるので、コミットサーバは、新しいメタデータを反映した新しいツリーを書き込むために使用される。少なくとも１つの実施態様では、ファイルサーバは、コミットサーバが実行しなければならない操作を、更新ログに記録する。更新ログは、コミットサーバによって取得され、更新ログ内に記述されている操作は、ファイルシステムの現在のイメージに適用され、データブロックストアに書き込まれる新しいメタデータブロック（例えば新しいファイルシステムバージョンを有する）となる。更新ログの各操作は、コミットサーバに操作を適用しなければならない順番を示すだけでなく、サーバがそのキャッシュされたデータをクリーン化プロセスを通してクリーン化できるようにするために使用されるタイムスタンプに、関連付けられている。]
[0006] 少なくとも１つの実施態様において、木の最新のバージョンは、ファイルサーバにキャッシュされているローカルデータとメタデータとを更新するために使用される。ファイルサーバは、木に対する最新の更新（たとえば、更新ログの最後の適用された操作）を示しているタイムスタンプに関連付けられている木のルートブロック（たとえば、スーパーブロック）を検索する。ストレージ木の最新のバージョンのルートブロックのタイムスタンプに基づいて、メタデータキャッシュ内のメタデータオブジェクトの古いバージョンが破棄され、実施態様によっては、ブロックストアの木の更新されたバージョンによって置き換えられる。]
[0007] 本発明のこれらの、そしてその他の利点は、以下の詳細な説明と添付の図面とを参照することによって、当業者に対して明らかになろう。]
図面の簡単な説明

[0008] 本発明の実施形態のストレージ装置の図である。
本発明の実施形態のファイルシステムの図である。
ストレージ装置に情報を保存する方法のフローチャートである。
本発明の実施形態の典型的なメタデータツリーの図である。
ファイルサーバでメタデータを保持する方法のフローチャートである。]
実施例

[0009] 従来の連想ストレージ装置（ＣＡＳ）をファイルシステムフロントエンド（例えばデータ入力）と組み合わせることによって、データが効率的にそして障害から早く回復されるように保存されている大きなファイルの高スループットの読み書きが可能になる。図１は、そのような組み合わせの実施形態を示している。ストレージ装置１００は、下位のＣＡＳをブロックストア１０６として使用して構築されている。ストレージ装置１００は、データの受信、作成、および／または修正（たとえばファイルへの書き込み）またはメタデータ操作（たとえば、新しいファイルのディレクトリへの挿入、ファイルに対する権限の変更など）が可能なファイルサーバ１０２などのインターフェイスを有している。ファイルサーバ１０２のデータは、ブロックストア１０６に書き込まれる。コミットサーバ１１２は、ファイルサーバから受信した操作を適用し、ファイルシステムメタデータを表しているデータブロックを、ファイルサーバ１０２インターフェイスとは独立に、またそれを考慮することなく、ブロックストア１０６に書き込むために使用される。このように、ストレージへのファイルサーバ１０２によるデータの書き込みとコミットサーバ１１２によるストレージへのメタデータの書き込みとは、非同期に実行され、効率的な高スループットの大きなファイルの読み書きを促進する。] 図１
[0010] 図１は本発明の実施形態のストレージ装置１００の図である。ストレージ装置１００は、クライアント１０４からデータ操作（ファイル書き込み、ファイル読み取り等）とメタデータ操作（例えばファイルの削除など）とを受信し、かつ、受信したデータをブロックストア１０６に保存される複数のデータブロックの塊にし、かつ、メタデータに適用される複数の操作の一覧をコミットサーバ１１２に送信する、ファイルサーバ１０２を有している。ブロックストア１０６は、複数のデータブロックを保存し、そのうちいくつかは、他の複数のデータブロックを指していることがあり、図２を参照して以降でさらに詳細に説明するファイルシステム１０８に編成されることができる。ブロックストア１０６は、コミットサーバ１１２がファイルシステム１０８を生成するために適用しなければならない操作を含んでいるログを保存する更新ログ１１０を、さらに有している。メタデータは、ファイルの内容ではない任意のデータである。例えば、メタデータは、ファイルやディレクトリ名、ファイル作成時間、ファイルサイズ、ファイルの権限などのクライアントが見ることができる１つまたは２つ以上のファイルについての情報、および／または、インデックス構造などのクライアントが見ることができない１つまたは２つ以上のファイルおよび／またはファイルシステムについての情報であってもよい。もちろん、他の適切なメタデータ（例えばデータ、１つまたは２つ以上のファイル、１つまたは２つ以上のデータブロック、１つまたは２つ以上のデータ構造、１つまたは２つ以上のファイルシステム、ビットマップ等についての情報）が使用されてもよい。更新ログ１１０は、コミットサーバによって適用されなければならない操作を記述している複数のレコードを、有していてもよい。そのような情報は、公知のように、ファイルシステム１０８の操作に必要な一時情報である。例えば、ファイルサーバ１１２は、データブロックをブロックストア１０６に書き込んだ後、更新ログ１１０を、つまり、データブロックのコンテンツアドレスを、データがその一部であってそのオフセットにデータが配置されているファイルを記述している情報ばかりではなく、以下でさらに詳しく説明するタイムスタンプと、共に送信する。] 図１ 図２
[0011] ファイルサーバ１０２は、クライアント１０４に結合されており、かつ、データ（例えば、情報、種類、ファイル等）の一時ストレージの位置を提供するように構成されている、コンピュータまたは他の装置であってもよい。そのため、ファイサーバ１０２は、ブロックストア１０６内に保存されている複数のデータブロックをキャッシュするブロックキャッシュ１１４と、メタデータ情報（たとえば、最近作られたファイル名）をキャッシュするメタデータキャッシュ１１６と、を有しているストレージおよび／またはメモリを有していてもよい。メタデータキャッシュ１１６の顕著な部分は、ファイルサーバ１０２によって最近書き込まれたデータブロックのコンテンツアドレスを保存するために使用される未コミットブロックテーブル１１８である。]
[0012] さらに、ファイルサーバ１０２は、クライアント１０４から受信したデータを複数のデータブロックの塊にして（たとえばデータブロックを生成して）、複数のデータブロックをブロックキャッシュ１１４に書き込む。つまり、ファイルサーバ１０２は、ＣＡＳ内に保存ができるように、クライアントデータから複数のデータブロックを作る、および／または、データをグループ分けし、それらのデータブロックをブロックストア１０６に書き込む。ブロックストア１０６は、データブロックを以前に見たことがある（既知、保存されていた等）と認識して、そのコンテンツアドレスを返すか、データブロックを新しいブロックとして認識して、そのコンテンツアドレスを生成し、コンテンツアドレスを返す。ファイルサーバ１０２は、ファイル操作（たとえばクライアント１０４からの書き込み操作）を処理しながら、メタデータキャッシュ１１６内にキャッシュされているメタデータを修正する。生成された複数のデータブロックは、データブロックストア１０６にできるだけ素早く書き込まれるが、これは、書き込みの完了後に初めてデータブロックがブロックキャッシュ１１４から取り除くことができるからである。書き込みが完了したという情報と共に受信されることもあるコンテンツアドレスは、ブロックキャッシュ１１４から取り除かれたデータブロックを再度フェッチするために使用することができる。書き込み操作が、書き込みデータを有する全てのブロックのコンテンツアドレスばかりではなく操作のタイムスタンプと共に、更新ログ１１０に追加される。ファイルサーバ１０２が、コミットサーバ１１２から、このタイムスタンプと同じかより大きいタイムスタンプを備えているスーパーブロック（図２に関して以下で説明）を受け取るまで、複数のデータブロックのコンテンツアドレスは、未コミットブロックテーブル１１８に保持される。未コミットブロックテーブル１１８は、データブロックストア１０６に保存されているが、ファイルシステム１０８のバージョンにはまだ現れていない（たとえば、方法３００に関して以下で説明するように、データブロックのアドレス情報は、コミットサーバ１１２によってファイルシステム１０８にまだ書き込まれていない）複数のデータブロックのコンテンツアドレスを保存している。ファイルシステム１０８の新しいバージョンが、コンテンツアドレスを含んでいる更新ログレコードの処理によって作られるまで、データブロックは、ファイルサーバ１０２上でファイルシステム１０８の古いバージョンを使用してアクセスすることができない。未コミットブロックテーブルを利用することによって、データブロックのコンテンツアドレスを容易に探して、クライアント１０４が要求すればデータブロックをフェッチすることができる。データブロックのメタデータを含んでいるファイルシステム１０８のバージョンが、いったんブロックストア１０６に書き込まれ、かつ、通知が、ファイルサーバ１０２によって受信されると、該当しているコンテンツアドレスが、未コミットブロックテーブル１１８から取り除かれることができる。] 図２
[0013] ブロックストア１０６は、ＣＡＳシステムまたは他の適切なメモリおよび／またはストレージ装置であってもよい。少なくとも１つの実施形態において、ブロックストア１０６は、どちらも参照によって本明細書に援用される２００８年１月３１日に提出された米国特許出願第１２／０２３，１３３号と、２００８年１月３１日に提出された米国特許出願第１２／０２３，１４１号に記載されているように、クラスタベースの連想ブロックストレージ装置である。もちろん、他のアドレスベースのストレージ装置を利用することもできる。]
[0014] ブロックストア１０６は、ファイルシステム１０８として編成可能な複数のデータブロックを含んでいる。ファイルシステム１０８は、木構造をエミュレートし、かつ、図２に関して以下でさらに詳細に説明する、データ構造である。ブロックストア１０６は、図３と方法３００とに関連して以下でより詳細に説明するように、メタデータのファイルシステム１０８への書き込みを促進する更新ログも有していてもよい。] 図２ 図３
[0015] コミットサーバ１１２は、ファイルサーバ１０２と同様の構造を有していてもよいが、ファイルシステム１０８のメタデータを更新するために使用することができる。コミットサーバ１１２は、ファイルサーバ１０２から受信した操作（たとえば、特定の名前を有しているファイルを特定のディレクトリで作成、特定のファイルへの特定のオフセットでの書き込みに相当しているコンテンツアドレスの挿入等）を処理する。更新ログ１１０の全ての操作は、タイムスタンプに関連付けられており、コミットサーバ１１２は、操作を、減少しない順番で単調に適用する。コミットサーバ１１２は、ファイルシステム１０８の新規のバージョンを生成する前にメタデータを保存するためのコミットメタデータキャッシュ１２０を有している。メタデータキャッシュ１１６と同様に、コミットメタデータキャッシュ１２０は、メタデータ、および／または、データブロックストア１０６に保存されているデータブロックのコンテンツアドレスなどのデータブロック情報を保存する。定期的に（例えば、所定の間隔で、コミットメタデータキャッシュ１２０が特定の使用レベルに到達したときに等）、メタデータおよび／またはデータブロック情報のバッチは、ファイルシステム１０８の新しいバージョンを生成するために使用される。それから、コミットサーバ１１２は、ファイルシステム１０８の新しいバージョンをブロックストア１０６に保存して、コミットメタデータキャッシュ１２０を消去する。]
[0016] ファイルサーバ１０２とコミットサーバ１１２とは、ログレコード（例えば、所与の名前のファイルを指定されたディレクトリに作る動作を記述しているなど）とその他の制御メッセージを交換することによって通信する。実施形態によっては、ログレコードは、ファイルサーバ１０２とコミットサーバ１１２との間で直接送信される。同じまたは代替の実施形態では、ログレコードは、ブロックストア１０６または他の位置に保存可能な更新ログ１１０に書き込まれる、および／または、更新ログ１１０において検索されてもよい。コミットサーバ１１２は、ファイルシステム１０８の現在のバージョンが常に存在するように動作する。つまり、コミットサーバ１１２は、ファイルシステム１０８の新しいバージョンを生成するために、（例えば更新ログ１１０の）ログレコードを決定して処理する。]
[0017] ストレージ装置１００は、ストレージ装置１００の全体の動作を定義するコンピュータプログラム命令を実行することによってストレージ装置１００の全体動作を制御する、プロセッサ（不図示）を有していてもよい。複数のコンピュータプログラム命令は、記憶装置（例えば磁気ディスク、データベース等）に保存する、および／または、複数のコンピュータプログラム命令の実行が必要なときにメモリにロードすることができる。したがって、本明細書で記述している方法３００と５００の方法ステップと、データ保存、データブロック生成、ファイルの読み取りおよび／または書き込み動作等のストレージ装置１００の関連する機能を実行するアプリケーションは、メモリ内に保存されているコンピュータプログラム命令によって定義されており、コンピュータプログラム命令を実行するプロセッサによって制御されている。ストレージ装置１００は、１つまたは２つ以上の中央処理装置、読み取り専用メモリ（ＲＯＭ）装置、および／またはランダムアクセスメモリ（ＲＡＭ）装置を有していてもよい。当業者には、実際の連想記憶ストレージ装置の実装は他の構成要素も有することができることと、図１のストレージ装置１００はそのようなストレージ装置の複数の構成要素のいくつかを図示の便宜上高レベルで表示していることが理解できるであろう。] 図１
[0018] 本発明のいくつかの実施形態によれば、プログラム（例えばコントローラソフトウェア）の命令は、例えばＲＯＭ装置からＲＡＭ装置へ、またはＬＡＮアダプタからＲＡＭ装置へのように、ファイルサーバ１０２、ブロックストア１０６、および／またはコミットサーバ１１２で読み取ることができる。プログラムの一連の命令の実行によって、方法３００と５００に関して前述した方法ステップのような１つまたは２つ以上の本明細書に記述されている方法ステップを、ストレージ装置１００に実行させることができる。代替の実施形態において、本発明の処理の実装のために、ハードウェアによって実現されている回路または集積回路を、ソフトウェア命令の代わりに、または、それらと組み合わせて使用することができる。したがって、本発明の実施形態は、ハードウェア、ファームウェア、および／またはソフトウェアの特定の組み合わせには一切限定されていない。ブロックストア１０６は、ソフトウェアプログラムを実行して、本発明に従って、特に詳述した方法に従って動作するように構成可能なストレージ装置１００用のソフトウェアを保存することができる。しかし、本明細書で記述している発明は、広範なプログラミング技法ばかりではなく汎用のハードウェアサブシステムまたは専用コントローラを使用して多くの様々な方法で実装できることが当業者には理解されるであろう。]
[0019] そのようなプログラムは、圧縮された、コンパイルされていない、および／または暗号化されている形式で保存することができる。プログラムはさらに、オペレーティングシステム、データベース管理システム、コントローラがコンピュータ周辺機器と接続できるようにするデバイスドライバ、他の装置／構成要素などの一般的に役立つプログラム要素を有している。適切な汎用プログラム要素が当業者には知られており、本明細書で詳細に記述する必要はない。]
[0020] 図２は、本発明の実施形態のファイルシステム１０８を示している。ファイルシステム１０８は、図１のストレージ装置１００のブロックストア１０６と共に、および／または、その一部と共に使用される。ファイルシステム１０８は、木構造をエミュレーションするメモリ内で実現されるデータ構造である。少なくとも１つの実施形態において、ファイルシステム１０８は、情報（例えば、メタデータ、アドレス、コンテンツアドレス等）の効果的な挿入、検索および削除を可能にする方法でデータを表しているストレージ木である。少なくとも１つの実施形態において、ファイルシステム１０８は、ｉｍａｐおよび各ｉｎｏｄｅの編成について知られているＢ＋ツリーを使用するが、任意の適切なツリーまたは他のデータ構造も使用することができる。] 図１ 図２
[0021] 同じまたは代替の実施形態において、ファイルシステム１０８は、データブロック２０２（たとえば、前述のようにファイルサーバ１０２から受信したデータブロック）および／または関連する情報などのファイル、ディレクトリ、および／またはシンボリックリンクがｉｎｏｄｅ２０４によって表されているＵｎｉｘ（登録商標）ライクな構造を有している。ｉｎｏｄｅ２０４は、データ、ファイル、他のデータ構造などについての基本情報（例えば、メタデータ、コンテンツ、アドレス等）を保存するそれ自体Ｕｎｉｘ（登録商標）ライクな構造内のデータ構造である。ｉｎｏｄｅ２０４は、ｉｎｏｄｅツリー２０６のルートブロックである。ｉｎｏｄｅツリー２０６は、Ｂ＋木であって、データブロック２０２のアドレスを使用してデータブロック２０２へのマッピングを実現してもよい。これによって、可変サイズのデータブロック２０２を使用してクライアント１０４の大きなファイルを収容することができる。]
[0022] それに対して、複数のｉｎｏｄｅ２０４の各々は、ｉｍａｐ木２１０の一部であるｉｍａｐブロック２０８内に個別のｉｎｏｄｅ番号によって索引付けされている。ｉｍａｐ木２１０は、ｉｍａｐ２１２であるルートブロックを有しているＢ＋木のようにそれ自体がデータ構造である。ｉｎｏｄｅ番号とデータブロック２０２のアドレスとの間の自動マッピングは存在しないため、ｉｍａｐ２１２はそれらの間の変換を促進している。これは、ログ構造ファイルシステムや他の適切なファイルシステムと同様である。ｉｍａｐ２１２は、ｉｍａｐ木２１０を有しており、固定サイズの複数のｉｍａｐブロック２０８に分割され、ｉｍａｐ木２１０によってインデックスが付けられている有効な複数のｉｎｏｄｅ番号と複数のｉｎｏｄｅ２０４のアドレスの配列である。複数のｉｎｏｄｅ２０４のマッピングとしてのｉｍａｐ２１２は、使用中のｉｎｏｄｅ番号と、対応する複数のｉｎｏｄｅ２０４の複数のコンテンツアドレスと、を追跡する。ｉｎｏｄｅの数が増加すると、そのコンテンツアドレスを保存するために、追加のｉｎｏｄｅブロック２０８がｉｍａｐ ２１２に追加される。大きすぎるデータ構造を作成することを避けるために、他のＵｎｉｘ（登録商標）ライクなファイルシステムに存在しているようなｉｎｏｄｅ番号を再使用する任意の戦略を採用することができる。]
[0023] ｉｍａｐ木２１０のルート、ｉｍａｐ２１２は、スーバーブロック２１４に保存されている。スーパーブロック２１４は、ｉｍａｐ２１２を指すポインタ、ファイルシステム１０８の複数のパラメータ、およびファイルシステム１０８のバージョン番号が組み込まれているブロックである。以下でさらに詳しく説明するように、ファイルシステム１０８が複数のスーパーブロック２１４を有することになるように新しいスーパーブロックが書き込まれるたびに、ファイルシステム１０８の新規のバージョンが作られる。つまり、ファイルシステム１０８は、ストレージ装置１１０のコミットサーバ１１２によって書き込まれた、ファイルシステム１０８の各バージョンについてスーパーブロック２１４を有している。最新のスーパーブロック２１４は、最新の情報の検索に使用することができる。他のスーパーブロック２１４は、過去に存在していた時のファイルシステムの「スナップショット」を検索するために使用することができる。]
[0024] 動作時には、ストレージ装置１１０は、ディスクベースのファイルシステムと同様に、ファイルの書き込み（たとえば、データブロックをブロックストア１０６に保存する）と、メタデータの更新（例えばファイルシステム１０８のバージョンをブロックストア１０６に保存する）と、を非同期に処理する。データブロックの保存のたびに新しいファイルシステム１０８のバージョンを書き込む代わりに、ストレージ装置１１０は、ファイルサーバ１０２がブロックキャッシュ１１４および／またはメタデータキャッシュ１１６の情報をすぐに利用して、新しいファイルシステム１０８をブロックストア１０６に後で書き込むことができるようにする。そうすることで、ストレージ装置１１０は、ファイルシステム１０８の複数の更新となるはずだった物を、コミットサーバ１１２による１つのファイルシステム１０８の書き込みにまとめることができる。さらに、クライアント１０４からの個別の読み取りおよび／または書き込み動作サービスを行うのに必要な時間を減らすことに加えて、これによってファイルシステム１０８を更新するコストを償却することができる。ファイルシステム１０８の新しいバージョンの書き込みには、ｉｎｏｄｅ木２０４内の各ブロックと、従ってスーパーブロック２１４に加えてｉｍａｐ木の更新が必要なため、複数の更新をそのようにまとめることによって、ｉｎｏｄｅ木とｉｍａｐ木の上位レベルを書き換えなければならない回数が減少する。さらに、これによって、ファイルシステム１０８の各バージョンにタイムスタンプを付けるか、ノードに作成および／または更新時間を付けることができる。そのようなタイムスタンプによって、クライアント１０４および／またはストレージ装置１００は、ファイルシステム１０８の以前のバージョンを検索し、したがって、データブロックストア１０６のデータブロックの以前のバージョンにアクセスすることができる。タイムスタンプは、単調に増加させることができる。実施形態によっては、タイムスタンプは単調に増加するが、実際の時間には基づいていない。]
[0025] 図３はストレージ装置１００に情報を保存する方法３００のフローチャートである。方法３００の複数の方法ステップは、ストレージ装置１００によって実行することができる。方法はステップ３０２から始まる。] 図３
[0026] ステップ３０４では、ファイルサーバ１０２において、データが、クライアント１０４から受信される。ステップ３０６において、データとメタデータとが、ファイルサーバ１０２によって、ブロックストア１０６から検索される。データは、ファイルシステム上での過去の操作に応じてデータブロックストア１０６に保存されている１つまたは２つ以上のデータブロックであってもよい。データブロックは、クライアント１０４によって要求される操作（例えばファイルの一部の上書き）を反映している新しい複数のブロックを生成するために使用できるように、ブロックストア１０６からフェッチすることができる。メタデータは、ディレクトリ、ファイルサイズ情報、ファイルの所有情報等を使用したｉｎｏｄｅへのファイル名のマッピングを有している。さらに、メタデータは、クライアント１０４には見えないデータブロックコンテンツアドレスなどの、ファイルシステム１０８からの情報であってもよい。]
[0027] ステップ３０８において、１つまたは２つ以上のデータブロックが生成される。ここで、ステップ３０４でクライアント１０４から受信したデータが、ファイルサーバ１０２によって、データブロックの塊にされる。複数のデータブロックが、従来の方法を使用して、ファイルサーバ１０２によって生成される。つまり、クライアント１０２からのデータに基づいて、別々の量のデータの複数のブロックが、ブロックファイルサーバ１０２によって作られる。さらに、各データブロックのコンテンツアドレスと他の関連するメタデータとが、書き込み完了通知と共に、ファイルサーバ１０２によって得られる。]
[0028] ファイルサーバ１０２は、ステップ３０４でクライアント１０４から受信したデータを、ファイルシステム１０８内のｉｎｏｄｅ２０４に関連付けられているバッファ（不図示）に蓄積する。クライアント１０４がファイルを開くときにファイルへのパスをクライアント１０４が提供すると、ファイルサーバ１０２は、このパスを使用して、ｉｎｏｄｅ２０４を検索し、クライアント１０４によるファイル上での以降の操作のためのコンテキストとしてそれを保持する。２つのブロックの境界は、同じデータの書き込みが同じブロックとなる可能性を増加させる区切りの点を見つけるために、クライアント１０２から受信したデータのコンテンツを検査することによって見出される。データブロックの境界が見つかると、その点までのバッファに保存されているデータは、新しいデータブロックを作るために使用される。バッファに残っているデータは、後続のデータブロックの全てまたは一部として使用される。実施形態によっては、メモリ消費を制限し、ｉｎｏｄｅバッファが限界なしに増大するのを防止するために、バッファされているデータの量の大局的な限界を採用することができる。]
[0029] ファイルサーバ１０２は、ブロックストア１０６が、ブロック書き込みを、ブロックのコンテンツアドレスを返すことによって確認するまで、ブロックキャッシュ１１４内に複数のデータブロックを保持する。コンテンツアドレスがいったん受信されると、ブロックは、ブロックキャッシュ１１４から取り除かれるが、これはコンテンツアドレスを使用してブロックを再度フェッチできるからである。]
[0030] ステップ３１０において、データブロックは、ブロックストア１０６に書き込まれ、複数のメタデータ操作が生成される。前述のように、ファイルサーバ１０２は、生成された複数のデータのブロックを、ブロックストア１０６に送信する。書き込みの結果修正する必要のある複数のデータブロックに関連しているあらゆるメタデータ操作（例えば、データブロックのコンテンツアドレス等）が、メタデータキャッシュ１１６に保存される。全てのメタデータ操作は、ファイルサーバ１０２によって、更新ログ１１０に記録される。メタデータ操作は、ブロックストア１０２および／またはファイルシステム１０８において実施される動作に関連している命令である。たとえば、データブロックが削除される場合、メタデータ操作は、データブロック（たとえば、図２のデータブロック２０２の１つ等）を削除するためのコミットサーバ１１２に対する命令である。もちろん、ファイルサーバ１０２からコミットサーバ１１２および／またはブロックストア１０６に送信される任意の適切な命令や操作を、メタデータ操作と見なしてもよい。] 図２
[0031] ブロックストア１０６は、１つまたは２つ以上のデータブロックの保存を確認し、データブロックを示しているコンテンツアドレスが、タイムスタンプ、ｉｎｏｄｅ番号、および新しく保存されたデータブロックに対応するバイト範囲と共に、未コミットブロックテーブル１１８に追加される。それから、ブロックキャッシュ１１４に保存されているデータブロックのコピーに、「クリーン」というマークが付けられる。つまり、それからコピーは、ブロックキャッシュ１１４から取り除く（例えば破棄する）ことができるとマークされることになる。]
[0032] ステップ３１２において、コミットサーバ１１２は、更新ログ１１０からメタデータ操作を検索する。実施形態によっては、更新ログ１１０は、ブロックストア１０６に保存されている。他の実施形態においては、コミットサーバ１１２は、メタデータ操作を直接ファイルサーバ１０２から検索する。]
[0033] コミットサーバ１１２が、メタデータ操作のバッチおよび／または複数のコンテンツアドレスを検索した後、コミットサーバは、ステップ３１４において、ファイルシステム１０８のバージョンを生成する。つまり、コミットサーバ１１２は、所定の量のメタデータが保存されるまで、複数のデータブロックを表しているメタデータを、コミットメタデータキャッシュ１２０に保存することができる。それから、コミットサーバ１１２は、コミットメタデータキャッシュ１２０内に保存されている全てのメタデータ操作を一括して処理して、ファイルシステム１０８の新しいバージョンを生成することができる。このようにして、コミットサーバ１１２は、ファイルシステム１０８の新しいバージョンを生成しなければならない回数を減少させる。]
[0034] 公知のように、コミットサーバは、ｉｎｏｄｅ２０６のｉｎｏｄｅ木２０４内のデータブロック２０２に関する情報をまず保存し、それからｉｍａｐ２１２内のｉｍａｐ木２１０のｉｎｏｄｅブロック２０８を通過してルート（例えばスーパーブロック２１４）までの経路を進むことによって、ボトムアップでファイルシステム１０８の新しいバージョンを生成することもできる。最後に、ルートブロック、つまりスーパーブロック２１４の新しいバージョンに加えて、このバージョンのファイルシステム１０８に寄与した最新のログレコードを示しているタイムスタンプが生成される。このようにして、各バッチ内の、したがってファイルシステム１０８の生成された各バージョン内のメタデータがわかるようになり、必要に応じてクライアント１０４および／またはストレージ装置１００によって呼び出すことができる。]
[0035] ステップ３１６では、ファイルシステム１０８の新しく生成されたバージョンが、ブロックストア１０６内に保存される。ファイルシステム１０８の新しいバージョンは、現在の該当しているバージョンとして以前のバージョンを置き換えるが、ファイルシステム１０８の１つまたは２つ以上の以前のバージョンを必ずしも上書きするわけではない。このように、ファイルシステム１０８の以前の複数のバージョンは、それらのそれぞれのタイムスタンプに従ってアクセスすることができる。したがって、古いデータブロックのアドレス情報を検索することもできる。]
[0036] ステップ３１８では、ファイルサーバ１０２は、ファイルシステム１０８のバージョンとタイムスタンプとを確定するために、ファイルシステム１０８にアクセスする。それから、ファイルサーバ１０２は、タイムスタンプを使用して、メタデータキャッシュ１１６内の「ダーティ」なメタデータを「クリーン」とマークすることができる。この情報は、図５に関して以下で説明するメタデータクリーン化方法５００と共に使用することができる。] 図５
[0037] 方法３００はステップ３２０で終了する。当然のことながら、方法３００のいくつかの方法ステップは、実施的に同時に実行可能である。例えば、ファイルサーバ１０４は、ステップ３０８で他のデータが複数のデータブロックを生成するために使用されるのと実質的に同時に、ステップ３０４でクライアント１０４からデータを受信してもよい。同様に、複数のデータブロックを、コミットサーバ１１２がブロックストア１０６でファイルシステム１０８のより新しいバージョンを生成し保存するのと実質的に同時に、ステップ３１０でブロックストア１０６に保存することができる。このように、ストレージ装置１００は、より素早く効果的にストレージとアドレス情報を更新することができる。]
[0038] 図４はメタデータキャッシュ１１６内に保存されているような典型的なメタデータ木４００を示している。メタデータ木４００は、ブロックストア１０６内のファイルシステム１０８を反映しており、構造的に同様なデータ構造である。言い換えると、メタデータ木４００は、本出願を通して説明したファイルシステムのデータ構造を記述する別な方法である。メタデータ木４００に含まれている情報は、方法３００のステップ３０６で検索されたようなファイルシステム１０８内のメタデータのコピーである。図４のメタデータオブジェクト４０２〜４１６は、各々関連付けられているタイムスタンプを有している。つまり、各メタデータオブジェクトは、単調カウンタである関連付けられている相対的な年齢を有している。最も大きい、関連付けられているカウンタ番号は、最近割り当てられた（例えば、最も新しい）情報に対応している。このように、より大きなカウンタ番号を備えているメタデータオブジェクトは、より小さいカウンタ番号を備えより古いつまりより最近ではないと考えられるメタデータオブジェクトよりも、新しいと考えることができる。] 図４
[0039] メタデータ木４００は、スーパーブロック４０２を有している。スーパーブロック４０２には、図２に関して前述したようにブロックストア１０６内のファイルシステム１０８のバージョンおよび／または対応しているバージョンのタイムスタンプに対応しているバージョン番号および関連付けられているタイムスタンプが割り当てられている。典型的なメタデータ木４００において、スーパーブロック４０２は、３７というバージョン番号と、関連付けられている７７９というタイムスタンプと、を有している。] 図２
[0040] ファイルシステム１０８と同様に、メタデータ木４００は、１つまたは２つ以上のｉｍａｐブロック４０４、４０６を有している。ｉｍａｐブロック４０４と４０６とは、７９７と８０５というそれぞれの関連付けられているタイムスタンプを有している。つまり、ｉｍａｐブロック４０４と４０６から延びている木の分岐の最新の情報は、タイムスタンプ７９７と８０５によってそれぞれ示されている。もちろん、スーパーブロック４０２は、それに依存している任意の数のｉｍａｐブロックを有していてもよい。]
[0041] ｉｍａｐブロック４０４と４０６とは、１つまたは２つ以上のｉｎｏｄｅにマップされていてもよい。例えば、ｉｍａｐブロック４０４は、各々がそれぞれの７８７と７９２というタイムスタンプを有しているｉｎｏｄｅ４０８と４１０にマッピングされていてもよい。同様に、ｉｍａｐブロック４０６は、各々がそれぞれの８０５と７９４というタイムスタンプを有しているｉｎｏｄｅ４１２と４１４にマッピングされていてもよい。もちろん、任意の数のｉｍａｐブロックおよび／またはｉｎｏｄｅを使用することができる。各オブジェクト（ｉｎｏｄｅ、ｉｍａｐブロック、スーパーブロック等）は、メタデータ木４００内の依存している任意のオブジェクトの最新のタイムスタンプと少なくとも同じほど新しいタイムスタンプを有している。]
[0042] メタデータ木４００は、スーパーブロック４１６などの新しいバージョンのスーパーブロックによって更新することができる。スーパーブロック４１６には、図２に関して前述したように、ブロックストア１０６内のファイルシステム１０８のバージョンおよび／または対応しているバージョンのタイムスタンプに対応しているバージョン番号とタイムスタンプとが割り当てられている。図４の典型的な実施形態では、スーパーブロック４１６は、３８というバージョン番号と８０２というタイムスタンプとを有している。その結果、スーパーブロック４１６は、スーパーブロック４０２よりも新しいと考えることができる。] 図２ 図４
[0043] メタデータ木４００は、単なる例であって、ストレージ装置１００と共に使用されるデータ構造の単純化版である。メタデータ木４００は、方法５００の複数の方法ステップを記述する場合に、単純化のために単純に分岐している木として表されている。]
[0044] 図５はファイルサーバ１０２でメタデータを保持する方法５００のフローチャートを示している。ファイルサーバ１０２内にメタデータを保持することは、メタデータキャッシュ１１６内で図４のメタデータ木４００などのメタデータ木を保持することを含んでいる。方法５００は、メタデータキャッシュ１１６を「クリーン化」つまり更新することと考えることができる。] 図４ 図５
[0045] メタデータオブジェクト（例えばメタデータオブジェクト４０２〜４１６）は、クリーン、ダーティ、または古いと指定されている。クリーンなオブジェクトは、かつて修正されたことがなく、前述の方法３００の方法ステップ３０６でファイルシステム１０８から検索されたオブジェクトであり、いずれかの時間にメタデータキャッシュ１１６から廃棄することができる。ダーティオブジェクトは、タイムスタンプが最新のスーパーブロックのタイムスタンプよりも大きいメタデータオブジェクトである。ダーティオブジェクトは破棄されないこともある。ダーティオブジェクトの親（例えばダーティオブジェクトが依存しているオブジェクト）は、ダーティでなくてはならない。古いオブジェクトは、タイムスタンプが最新のスーパーブロックのタイムスタンプよりも小さいメタデータオブジェクトである。古いオブジェクトは、いつ廃棄してもよい。ファイルサーバは、ブロックに保存されているコンテンツアドレスの１つを使用する場合、古いブロックをブロックストア１０６から再度フェッチしなければならないが、古いオブジェクトは、いくつかの現在のコンテンツアドレスを含んでいてもよい。古いブロックの新しくそして更新されているバージョンは、更新されたブロックの子を書き込んでいるときにコミットサーバ１１２によって生成された異なるコンテンツアドレスを有していてもよい。古いオブジェクトの親は、古いまたはダーティであって、他のダーティな子を有していてもよい。]
[0046] 方法５００はステップ５０２から始まる。]
[0047] ステップ５０４において、メタデータ操作が、メタデータキャッシュ１１６で受信される。そのようなメタデータ操作は、図４のスーパーブロック４１６のようなスーパーブロックの新しいバージョンを有していてもよい。スーパーブロックの新しいバージョンは、ファイルシステム１０８のコミットサーバ１１２によるボトムアップの書き込みに基づいていてもよい。コミットサーバ１１２は、タイムスタンプの順に、まとめて、このメタデータを処理する。コミットサーバ１１２は、このまとまりの中のメタデータのうちの最も新しいメタデータのタイムスタンプであるスーパーブロック（たとえばルートブロック）タイムスタンプを、このまとまりに対して生成する。コミットサーバ１１２は、前述のようにファイルシステム１０８の木に従って、ファイルシステム１０８の複数の修正されたブロックを、ボトムアップから書き込む。ファイルシステム１０８のスーパーブロックは、必ず最後に書き込まれるブロックであり、適切な時間に（例えばフェッチされたときに）メタデータキャッシュ１１６に渡される。] 図４
[0048] ステップ５０６で、受け取ったスーパーブロックのタイムスタンプに基づいて、必要に応じて、メタデータオブジェクトは古いと指定される。つまり、受信したスーパーブロックのタイムスタンプよりも古いどのようなダーティなオブジェクトも古いと指定される。]
[0049] 図４の典型的な実施形態において、ｉｍａｐブロック４０４と４０６とｉｎｏｄｅ４０８〜４１４は、全て初期状態でダーティであるが、それは、それらのタイムスタンプがスーパーブロック４０２の初期のタイムスタンプよりも新しい（たとえば大きい）からである。そのため、タイムスタンプが８０２であるスーパーブロック４１６が受信されたときに、ｉｍａｐブロック４０４は古いと指定されるが、それはｉｍａｐブロック４０４がスーパーブロック４１６よりも古い（たとえば小さい）タイムスタンプ（７９７）を有しているからである。同様に、ｉｎｏｄｅ４０８、４１０、および４１４も古いと指定されるが、これは、それらのタイムスタンプもスーパーブロック４１６のタイムスタンプよりも古いからである。] 図４
[0050] ステップ５０８では、複数の古いメタデータオブジェクトが破棄される。古いメタデータオブジェクトは、メタデータ木（例えばメタデータ木４００）に従ってトップダウンで破棄される。複数のメタデータオブジェクトをトップダウンで破棄することで、破棄されたオブジェクトが、その古い親から得られた古いコンテンツアドレスを使用してファイルシステム１０８から再度フェッチされないことが保証される。その結果、古い子は、その親をまず破棄しないで破棄することはできない。メタデータオブジェクトは、木の依存性のチェーンに従って破棄される。典型的なメタデータ木４００において、スーパーブロック４０２がまず破棄され、それに続いて、ｉｍａｐブロック４０４と４０６が破棄され、最後にｉｎｏｄｅ ４０８〜４１４が破棄される。]
[0051] 図４の典型的な実施形態において、ｉｍａｐブロック４０４とその子のｉｎｏｄｅ４０８と４１０は古く、破棄され、ｉｎｏｄｅ４１４も、ステップ５０６で判断されたように古いが、その親であるｉｍａｐブロック４０６は古くないため、破棄することができない。] 図４
[0052] 実施形態によっては、破棄されたメタデータオブジェクトは置き換えられる。そのような置き換えは、任意である。たとえば、ファイルをディレクトリから取り除いた後、そのディレクトリではさらなる操作は実行されない。したがって、そのディレクトリを保存し続ける必要はない。破棄されたメタデータオブジェクトは、ファイルシステム１０８の複数のバージョンによって置き換えられる。図４の典型的な実施形態では、スーパーブロック４０６に対応しているｉｍａｐブロック４０４とｉｎｏｄｅ４０８と４１０のより新しいバージョンが、ファイルシステム１０８から検索され、メタデータキャッシュ１１６に保存される。] 図４
[0053] 方法５００はステップ５１０で終了する。]
[0054] 前述の発明を実施するための最良の形態は、あらゆる観点において、例示的で典型的であって、限定的ではないと理解されるべきであり、本明細書において開示している本発明の範囲は、発明を実施するための最良の形態から定められるのではなく、むしろ、特許法によって認められる全範囲に従って解釈されるように特許請求の範囲から定められる。当然、本明細書で示し詳述した実施形態は、本発明の原理を単に例示しており、当業者は本発明の範囲と精神から逸脱することなくさまざまな修正を実装することができる。当業者は、本発明の範囲と精神から逸脱することなく、様々な他の特徴の組み合わせを実装することができる。]

权利要求:

請求項1
ファイルサーバを使用してデータを１つまたは２つ以上のデータのブロックの塊にし、前記ファイルサーバを使用してファイルシステムの複数のメタデータ操作を生成し、前記１つまたは２つ以上のデータのブロックをブロックストアに保存し、コミットサーバを使用して前記複数のメタデータ操作を検索し、前記コミットサーバを使用して前記複数のメタデータ操作と前記１つまたは２つ以上のデータのブロックとに基づいてデータ構造を生成し、前記データ構造を前記ブロックストアに保存することを含む、情報をストレージシステムに保存する方法。
請求項2
前記複数のメタデータ操作を更新ログに保存することをさらに有し、前記コミットサーバを使用して前記複数のメタデータ操作を検索することは、前記複数のメタデータ操作を前記更新ログから検索することを有する、請求項１に記載の方法。
請求項3
前記１つまたは２つ以上のデータのブロックを前記ブロックストアに保存することと、前記データ構造を前記ブロックストアに保存することとは、実質的に同時に起こる、請求項１に記載の方法。
請求項4
前記ファイルサーバでクライアントからデータを受信することをさらに有し、前記ファイルサーバを使用して前記データを前記１つまたは２つ以上のデータのブロックの塊にすることは、前記クライアントから受信した前記データを前記１つまたは２つ以上のデータのブロックに分離することを有する、請求項１に記載の方法。
請求項5
前記ファイルサーバを使用して、前記データを前記１つまたは２つ以上のデータのブロックの塊にすることと前記複数のメタデータ操作を生成することとは、前記生成された複数のメタデータ操作にタイムスタンプを関連付けることをさらに有し、前記複数のメタデータ操作を前記ファイルサーバに保存することと、前記検索された複数のメタデータ操作に関連付けられている１つまたは２つ以上の前記タイムスタンプの少なくとも一部に基づいて、前記ファイルサーバに保存されているメタデータを、前記データ構造のバージョンとして保存されているメタデータでクリーンにすることと、を有する、請求項２に記載の方法。
請求項6
前記コミットサーバを使用して前記メタデータを有する前記データ構造を生成することは、前記検索された複数のメタデータ操作に関連付けられている前記１つまたは２つ以上のタイムスタンプを検索することと、前記検索された複数のメタデータ操作に基づいて、メタデータキャッシュ内のメタデータを修正することと、前記複数のメタデータ操作を１つにまとめることと、前記検索されたメタデータに関連付けられている前記１つまたは２つ以上のタイムスタンプの少なくとも一部に基づく前記メタデータを前記データ構造のバージョンとして保存することと、を有する、請求項２に記載の方法。
請求項7
データを複数のデータのブロックの塊にし、複数のメタデータ操作を生成するように構成されているファイルサーバと、前記複数のデータのブロックを保存するように構成されているメモリと、前記複数のメタデータ操作を検索し、前記複数のメタデータ操作を示しているデータ構造を生成し、前記データ構造を前記メモリ内に保存するように構成されているコミットサーバと、を有する、データを保存するシステム。
請求項8
前記複数のメタデータ操作を前記ファイルサーバから検索して、前記複数のメタデータ操作を前記コミットサーバに渡すように構成されている更新ログさらに有する、請求項７に記載のシステム。
請求項9
関連付けられているタイムスタンプと、関連付けられているタイムスタンプを有している１つまたは２つ以上のメタデータオブジェクトと、を有している第１のスーパーブロックを有するファイルサーバでメタデータ構造を保持する方法であって、前記第１のスーパーブロックのカウンタ番号よりも高いカウンタ数を有する関連付けられているタイムスタンプを備えている第２のスーパーブロックを受信し、１つまたは２つ以上のメタデータオブジェクトの少なくとも１つを、前記第２のスーパーブロックの前記タイムスタンプと、１つまたは２つ以上の依存メタデータオブジェクトのタイムスタンプと、に基づいて、古くなったと指定し、古くなったと指定された前記１つまたは２つ以上のメタデータオブジェクトを破棄すること、を有する方法。